The present invention relates to improved data processing method, and more specifically, to method for providing multiple level linked least recently used (LRU) priority regarding resource allocation.
In a computer system, technology advancements allow more processors and other components on a single chip. This results in an increasing number of requestors vying for access to a shared resource. An LRU scheme is typically used; however it may require a large number of latches for arbitration between requestors. For example, selecting the oldest among four requestors may require six LRU latches, while selecting the oldest from 16 requestors may require 120 LRU latches. In addition, to logic complexity, physical restraints are also an issue, such as the amount of space on the chip, cycle time delay and power constraints.
One typical method has been to divide the requestors having a same priority into smaller groups. For example, dividing 16 requestors into four groups of four requestors. Therefore, six LRU latches would be used for each of the four groups to determine the LRU requestor. Then a second level of LRU is performed on the winning LRU requestor from each of the four groups with the use of six LRU latches. Although a reduced number of LRU latches are utilized with this method, a significant portion of the integrity of the LRU algorithm is lost by dividing the requestors into groups, thereby resulting in possible requestor lockouts.